import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.Vector;

public class DijkstraAlgorithm {
	private TransitGraph graph;
	private final ArrayList<Station> stations;
	private final ArrayList<Edge> edges;
	private Set<Station> settledNodes;
	private Set<Station> unSettledNodes;
	private Map<Station, Station> predecessors;
	private Map<Station, Integer> distance;
	private Integer start_time;

	public DijkstraAlgorithm(TransitGraph graph) {
		// Create a copy of the array so that we can operate on this array
		this.stations = new ArrayList<Station>(graph.getStationsList());
		this.edges = new ArrayList<Edge>(graph.getEdges());
		this.graph = graph;
		start_time = null;
	}

	public void setStarttime(int mins) {
		start_time = mins;
	}
	
	public Integer getStarttime() {
		return start_time;
	}
	
	public void execute(Station source) {
		if(start_time == null) {
			System.out.println("Error: Start time required!");
			return;
		}
		
		settledNodes = new HashSet<Station>();
		unSettledNodes = new HashSet<Station>();
		distance = new HashMap<Station, Integer>();
		predecessors = new HashMap<Station, Station>();
		distance.put(source, 0);
		unSettledNodes.add(source);
		while (unSettledNodes.size() > 0) {
			Station node = getMinimum(unSettledNodes);
			settledNodes.add(node);
			unSettledNodes.remove(node);
			findMinimalDistances(node);
		}
	}

	private void findMinimalDistances(Station station) {
		List<Station> adjacentNodes = getNeighbors(station);
		for (Station target : adjacentNodes) {
			int dist = getDistance(station, target);
			if(dist == 0) {	
				int time = target.getClosestTime(start_time + distance.get(station));
				dist = time - (start_time + distance.get(station)); // TODO doesn't handle 23 to 0 overflow
			} else if(dist == -1) { // Parent station
				dist = 0;
			}
			
			if (getShortestDistance(target) > getShortestDistance(station) + dist) {		
				distance.put(target, getShortestDistance(station) + dist);
				predecessors.put(target, station);
				unSettledNodes.add(target);
			}
		}

	}

	private int getDistance(Station station, Station target) {
		for (Edge edge : edges) {
			if (edge.getSource().equals(station)
					&& edge.getDestination().equals(target)) {
				return edge.getWeight();
			}
		}
		throw new RuntimeException("Should not happen");
	}

	private List<Station> getNeighbors(Station station) {
		List<Station> neighbors = new ArrayList<Station>();
		for (Edge edge : edges) {
			if (edge.getSource().equals(station)
					&& !isSettled(edge.getDestination())) {
				neighbors.add(edge.getDestination());
			}
		}
		return neighbors;
	}

	private Station getMinimum(Set<Station> stations) {
		Station minimum = null;
		for (Station station : stations) {
			if (minimum == null) {
				minimum = station;
			} else {
				if (getShortestDistance(station) < getShortestDistance(minimum)) {
					minimum = station;
				}
			}
		}
		return minimum;
	}

	private boolean isSettled(Station vertex) {
		return settledNodes.contains(vertex);
	}

	private int getShortestDistance(Station destination) {
		// TODO: Add weights to edges with no value
		Integer d = distance.get(destination);
		if (d == null) {
			return Integer.MAX_VALUE;
		} else {
			/*if(d == 0) {
				System.out.println("transfer: " + d + " " + distance.get(destination));
			}*/
			return d;
		}
	}

	/*
	 * This method returns the path from the source to the selected target and
	 * NULL if no path exists
	 */
	public ArrayList<StationPair> getPath(Station target) {
		ArrayList<StationPair> path = new ArrayList<StationPair>();
		Station step = target;
		// Check if a path exists
		if (predecessors.get(step) == null) {
			return null;
		}
		StationPair spair = new StationPair(step, distance.get(step));
		path.add(spair);
		while (predecessors.get(step) != null) {
			step = predecessors.get(step);
			spair = new StationPair(step, distance.get(step));
			path.add(spair);
		}
		// Put it into the correct order
		Collections.reverse(path);
		return path;
	}

}